package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

public class PThree4在排序数组中查找元素的第一个和最后一个位置{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //先找>=target的第一个
    //再找>target的第一个
    //我真是这辈子都不想看见这题
    //
    //根本不用管大于小于，直接找等于的，
    //先找到等于的最左边，在找等于的最右边
    public int[] searchRange(int[] nums, int target) {
        if(nums==null ||nums.length==0) return new int[]{-1,-1};
        int l=binSearchLeft(nums,0,nums.length-1,target);
        int r=binSearchRight(nums,0,nums.length-1,target);
        return new int[]{l,r};
    }
    //找>=target的第一个
    public int binSearchLeft(int[] nums,int left,int right,int target){
        int ans = -1;
        while (left<=right){
            int m = left+(right-left)/2;
            if(target<nums[m]){
//                ans = m;   // 找到插入位置
                right=m-1;
            }else if (nums[m]<target){
                left=m+1;
            }else {
                ans = m;
                right = m-1; // 相同靠左
            }
        }
        return ans;
    }
    public int binSearchRight(int[] nums,int left,int right,int target){
        int ans = -1;
        while (left<=right){
            int m = left+(right-left)/2;
            if(target<nums[m]){
//                ans = m;   // 找到插入位置
                right=m-1;
            }else if (nums[m]<target){
                left=m+1;
            }else {
                ans = m;
                left = m+1;  // 相同靠右
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PThree4在排序数组中查找元素的第一个和最后一个位置().new Solution();
        int[] ints = solution.searchRange(new int[]{1}, 1);
        System.out.println(Arrays.toString(ints));
    }
}